package newcoder.t3;

import java.util.ArrayList;
import java.util.List;

public class Solution {

    private ArrayList<String> result = new ArrayList<>();

    public static void main(String[] args) {
//        long l = System.currentTimeMillis();
//        int[] array = {1, 3, 3, 3, 3, 4, 5};
//        int i = GetNumberOfK(array, 2);
//        System.out.println(i);
//        System.out.println(System.currentTimeMillis() - l);

//        int[][] nums = {{1, 1}};
//        boolean find = Find(1, nums);
//        System.out.println(find);

//        int[] array = {3,4,5,1,2};
//        int min = findMin(array);
//        System.out.println(min);

        Solution solution = new Solution();
        ArrayList<String> ab = solution.Permutation("ab");
        ab.forEach(str->{
            System.out.println(str);
        });

    }

    public static int GetNumberOfK(int[] array, int k) {
        int length = array.length;
        if (length == 0) {
            return 0;
        }
        if (array[0] > k || array[length - 1] < k) {
            return 0;
        }
        int start = 0, end = length;
        int index = 0;
        while (start < end) {
            index = (start + end) / 2;
            if (array[index] == k) {
                break;
            } else if (array[index] > k) {
                end = index;
            } else {
                start = index + 1;
            }
        }
        if (array[index] != k) {
            return 0;
        }
        int count = 1;
        int left = index - 1, right = index + 1;
        while (left >= 0) {
            if (array[left] == k) {
                count++;
                left--;
            } else {
                break;
            }
        }
        while (right < length) {
            if (array[right] == k) {
                count++;
                right++;
            } else {
                break;
            }
        }
        return count;
    }

    public static boolean Find(int target, int[][] array) {
        int height = array.length;
        if (height == 0) {
            return false;
        }
        int cross = array[0].length;
        if (cross == 0) {
            return false;
        }
        int x = height - 1, y = 0;
        while (x >= 0 && y >= 0 && x < height && y < cross) {
            if (array[x][y] < target) {
                y++;
            } else if (array[x][y] > target) {
                x--;
            } else {
                return true;
            }
        }

        return false;

//        int startX = 0, startY = 0;
//        int endX = cross, endY = height;
//
//        while (startX < endX && startY < endY) {
//            int x = (startX + endX) / 2, y = (startY + endY) / 2;
//            if (array[x][y] == target) {
//                return true;
//            } else if (array[x][y] < target) {
//                startX = x + 1;
//                startY = y + 1;
//            } else {
//                endX = x;
//                endY = y;
//            }
//        }
//        return false;
    }

    public static int findMin(int[] array) {
        int length = array.length;
        int start = 0, end = length - 1;
        int middle = (start + end) / 2;
        int min = array[0];
        while (start < end) {
            if (array[start] == array[middle] && array[middle] == array[end]) {
                for (int i = 1; i < array.length; i++) {
                    if (array[i] < min) {
                        min = array[i];
                    }
                }
                return min;
            } else if (array[middle] < array[start]) {
                end = middle;
                min = array[middle];
            } else if (array[middle] > array[start]) {
                start = middle;
            }
            else if(array[middle] > array[end]){
                start = middle;
            }
            else{
                end = middle;
            }
            if (start == end -1){
                break;
            }
            middle = (start+end)/2;
        }
        return array[end]>array[start]?array[start]:array[end];
    }

    public ArrayList<String> Permutation(String str) {
        ArrayList<Character> list = new ArrayList<>();
        for (char c : str.toCharArray()) {
            list.add(c);
        }
        Solution solution = new Solution();
        char[] temp = new char[str.length()];
        solution.back(temp,0,list);
        return solution.result;
    }

    public void back(char[] temp, int index,List<Character> charList){
        int length = charList.size();
        if (length == 1){
            temp[index] = charList.get(0);
            result.add(new String(temp));
            return;
        }
        List<Character> distinct = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            Character character = charList.get(i);
            if (distinct.contains(character)) {
                continue;
            }
            distinct.add(character);
            temp[index] = character;
            Character remove = charList.remove(i);
            back(temp,index+1,charList);
            charList.add(i,remove);
        }
    }
}
